package leetcodehot;

public class leetcode19_removeNthFromEnd {
    /**
     * 删除链表倒数第n个数
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     */


    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }


    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode tmp = head;
        int last = length(head) - n;
        if (last == 0) {
            return head.next;
        }
        //找到要删除得链表并赋值给他们
        for (int i = 0; i < last - 1; i++) {
            //遍历1-n位置得链表 cur指向n-1
            tmp = tmp.next;
        }
        //cur = n-1 next跳过n cur.next = cur.next.next
        tmp.next = tmp.next.next;
        return head;


        /*/
        //定义tmp指针 只想head 定义当前cur 指向head.next 定义链表长度默认为1
        ListNode tmp = head;
        //head长度
        int last = (length(head) - n);

        int curPositio = 1;
        ListNode cur = head.next;
        //n为链表长度 就直接返回head.next
        if(last ==0) return head.next;
        //cur链表不为空 循环。如果记录长度=last
        while (cur != null) {
            if (curPositio == last) {
                tmp.next = cur.next;
                break;
            }
            curPositio++;
            tmp = tmp.next;
            cur = cur.next;
        }
        return head;
         */
    }

    //计算链表长度
    private int length(ListNode head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }

}
